package cn.harperDog.algrithm;

/**
 * @author hua
 * @description
 * @date 2022/2/28
 *
 * 获取两个字符串最大的公共子串
 *
 * 思路一：
 *      用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置.
 *
 *      当字符匹配的时候，不是简单的给相应元素赋上1，而是赋上其左上角元素的值加1。我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判断当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。
 *
 *      a    c    b    a    c
 *
 * a   1    0    0    1    0
 *
 * c   0    2    0    0    2
 *
 * a   1    0    0    1    0
 *
 * c   0    2    0    0    2
 *
 * c   0    1    0    0    1
 *
 * b   0    0   2    0    0
 *
 * a   1    0    0    3    0
 *
 * b   0    0    1    0    0
 *
 * b   0    0    1    0    0
 */
public class PubStrTest {
    public static void main(String[] args) {
        String str1 = "abdcsldlslflsal";
        String str2 = "abddasdlslflsalsdfdfs";

        char[] c1 = str1.toCharArray();
        char[] c2 = str2.toCharArray();

        Record record = new Record();

        int max = maxCommonLength(c1, c2, record);

        System.out.println(record);

        //打印出最长子串
        for (int i = record.markI + 1 - max, j = record.markJ + 1 - max, counter = 0;
             counter < max; i++, j++, counter++) {
            System.out.print(c1[i]);
        }
    }

    private static int maxCommonLength(char[] str1, char[] str2, Record record) {
        int[][] matrix = new int[str1.length][str2.length];

        for (int i = 0; i < str1.length; i++) {
            for (int j = 0; j < str2.length; j++) {
                if (str1[i] == str2[j]) {
                    matrix[i][j] = matrix[i - 1 >= 0 ? i - 1 : 0][j - 1 >= 0 ? j - 1 : 0] + 1;
                } else {
                    matrix[i][j] = 0;
                }

                if (record.length < matrix[i][j]) {
                    record.length = matrix[i][j];
                    record.markI = i;
                    record.markJ = j;
                }
            }
        }

        return record.length;
    }
}

class Record {
    int length = 0;
    int markI = -1;
    int markJ = -1;

    @Override
    public String toString() {
        return "Record{" +
                "length=" + length +
                ", markI=" + markI +
                ", markJ=" + markJ +
                '}';
    }
}
